/**
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1
和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
#include <limits.h>
#include <math.h>
#include <vector>
using namespace std;
class Solution {
  public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        double result = 0;
        int length1 = nums1.size();
        int length2 = nums2.size();
        int left = 0;
        int right = length1;

        while (left <= right) {
            int i = (left + right) / 2;
            int j = (length1 + length2 + 1) / 2 - i;
            int n1_im1 = i <= 0 ? INT_MIN : nums1[i - 1];
            int n1_i = i >= length1 ? INT_MAX : nums1[i];
            int n2_jm1 = j <= 0 ? INT_MIN : nums2[j - 1];
            int n2_j = j >= length2 ? INT_MAX : nums2[j];
            if (n1_im1 <= n2_j) {
                if ((length1 + length2) % 2) {
                    //奇数
                    result = max(n1_im1, n2_jm1);
                } else {
                    //偶数
                    result = (max(n1_im1, n2_jm1) + min(n1_i, n2_j)) / 2.0;
                }
                left = i + 1;
            } else {
                right = i - 1;
            }
        }
        return result;
    }
};